/*
 * @lc app=leetcode.cn id=42 lang=javascript
 *
 * [42] 接雨水
 */

// @lc code=start
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  //   let sum = 0
  //   let len = height.length
  //   for (let i = 1; i < len - 1; i++) {
  //     const left = getMaxValue(height, 0, i)
  //     const right = getMaxValue(height, i + 1, len)
  //     let h = Math.min(left, right) - height[i]
  //     h = h < 0 ? 0 : h
  //     sum += h
  //   }
  //   // console.log(sum)
  //   return sum
  // }
  // function getMaxValue (height, left, right) {
  //   let maxValue = 0
  //   for (let i = left; i < right; i++) {
  //     maxValue = Math.max(maxValue, height[i])
  //   }
  //   return maxValue
  const n = height.length;
  if (n === 0) {
    return 0
  }
  const leftMax = new Array(n).fill(0)
  // 初始值
  leftMax[0] = height[0]
  for (let i = 1; i < n; ++i) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i])
  }
  // console.log(leftMax)
  
  const rightMax = new Array(n).fill(0)
  // 初始值
  rightMax[n - 1] = height[n - 1]
  for (let i = n - 2; i >= 0; --i) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i])
  }
  // console.log(rightMax)
  
  let ans = 0
  for (let i = 0; i < n; ++i) {
    ans += Math.min(leftMax[i], rightMax[i]) - height[i]
  }
  return ans
}
// trap([0,1,0,2,1,0,1,3,2,1,2,1])
// @lc code=end

